<!doctype html>
<html lang="en-us">
<head>

    <meta charset="utf-8">
    <meta name="generator" content="Hugo 0.59.1" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>队列 | 林贤钦</title>
    <meta property="og:title" content="队列 - 林贤钦">
    <meta property="og:type" content="article">
        
    <meta property="article:published_time" content="2020-04-14T09:39:42&#43;08:00">
        
        
    <meta property="article:modified_time" content="2020-04-14T09:39:42&#43;08:00">
        
    <meta name="Keywords" content="java,博客,项目管理,软件架构,公众号,小程序">
    <meta name="description" content="队列">
        
    <meta name="author" content="林贤钦">
    <meta property="og:url" content="http://linxianqin.gitee.io/post/%E9%98%9F%E5%88%97/">
    <link rel="shortcut icon" href="/img/favicon.ico" type="image/x-icon">

    <link rel="stylesheet" href="/css/normalize.css">
    
        <link rel="stylesheet" href="/css/prism.css">
    
    <link rel="stylesheet" href="/css/style.css">
    <script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>

    


    
    
</head>

<body>
<header id="header" class="clearfix">
	<div class="container">
        <div class="col-group">
            <div class="site-name ">
                
                    <a id="logo" href="http://linxianqin.gitee.io">
                        林贤钦
                    </a>
                
                <p class="description">专注于Java、微信小程序、移动互联网、项目管理、软件架构</p>
            </div>
            <div>
                <nav id="nav-menu" class="clearfix">
                    <a class="current" href="http://linxianqin.gitee.io">首页</a>
                    
                    <a  href="http://linxianqin.gitee.io/archives/" title="归档">归档</a>
                    
                    <a  href="http://linxianqin.gitee.io/about/" title="关于">关于</a>
                    
                </nav>
            </div>
        </div>
    </div>
</header>


<div id="body">
        
        
    <div class="container">
        <div class="col-group">

            <div class="col-8" id="main">
                <div class="res-cons">
                    <article class="post">
                        <header>
                            <h1 class="post-title">队列</h1>
                        </header>
                        <date class="post-meta meta-date">
                            2020年4月14日
                        </date>
                        
                        <div class="post-meta">
                            <span>|</span>
                            
                                <span class="meta-category"><a href="http://linxianqin.gitee.io/categories/java">java</a></span>
                            
                                <span class="meta-category"><a href="http://linxianqin.gitee.io/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</a></span>
                            
                        </div>
                        
                        
                        <div class="post-meta">
                            <span id="busuanzi_container_page_pv">|<span id="busuanzi_value_page_pv"></span><span> 阅读</span></span>
                        </div>
                        
                        
                        <div class="post-content">
							<nav id="TableOfContents">
<ul>
<li>
<ul>
<li><a href="#什么是队列">什么是队列</a>
<ul>
<li><a href="#顺序队列">顺序队列</a></li>
<li><a href="#循环队列">循环队列</a></li>
</ul></li>
</ul></li>
</ul>
</nav>
                            

<h2 id="什么是队列">什么是队列</h2>

<p><strong>队列是一种先进先出（First in First Out）的线性表，简称FIFO</strong>，<strong>允许插入的一端称为队尾，允许删除的一端称为队头</strong></p>

<p>最简单的来说就是“先进先出，先来先服务，站前面，后来后服务往最后站，排队，不准插队”</p>

<h3 id="顺序队列">顺序队列</h3>

<p>简单来理解就是，我给定一个一条队伍的位置，比如5个，第一个来的站第一个，第二个来的站第二个，直达第五个人占第五个，然后出队的时候，我先找第一个，然后第一个出去，其余人不动，我一次找下去直到第五个人出完队</p>

<p>顺序队列通常采用一维数组进行存储，如图：</p>

<p><img src="../imgdataStructureArrayQueue.jpg" alt="顺序队列" /></p>

<p>用数组实现一个顺序队列</p>

<p>队列的四个属性</p>

<pre><code class="language-java">  	private int maxSize;//表示数组最大的容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //存放数据，模拟队列
</code></pre>

<p>创建顺序队列的时候必须创建输入数组的大小arrMaxSize</p>

<pre><code class="language-java">public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr = new int[maxSize];
        front =-1; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1; //指向队列尾 ， 指向队列尾的数据(也就是队列最后的一个数据)
    }
</code></pre>

<p>判断队列为空 rear == front == -1</p>

<pre><code class="language-java"> return  rear == front;
</code></pre>

<p>判断队列是否满(rear达到数组最大下标的值)</p>

<pre><code class="language-java">return rear == maxSize -1;
</code></pre>

<p>进队&mdash;&gt;后来的往后面排队加入队列、</p>

<pre><code class="language-java">public void addQueue(int n){
    //判断队列是否满了
    if (isFull()){
        System.out.println(&quot;队列满，不能加入数据了&quot;);
        return;
    }
    rear++; //rear后移
    arr[rear] = n;
}
</code></pre>

<p>出队&mdash;&gt;先进的先出、先来的先进队列，后来的不动。</p>

<pre><code class="language-java">//获取队列数据，出队列
public  int getQueue(){
    //判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException(&quot;队列空，不能取得数据&quot;);
    }
    front++;
    return arr[front];
}
</code></pre>

<p>具体代码：</p>

<pre><code class="language-java">public class ArrayQueue {
    private int maxSize;//表示数组最大的容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //存放数据，模拟队列
    public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr = new int[maxSize];
        front =-1; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1; //指向队列尾 ， 指向队列尾的数据(也就是队列最后的一个数据)
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize -1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return  rear == front;
    }
    //添加数据到队列，进队
    public void addQueue(int n){
        //判断队列是否满了
        if (isFull()){
            System.out.println(&quot;队列满，不能加入数据了&quot;);
            return;
        }
        rear++; //rear后移
        arr[rear] = n;
    }
    //获取队列数据，出队列
    public  int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException(&quot;队列空，不能取得数据&quot;);
        }
        front++;
        return arr[front];
    }
    //显示队列所有的数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println(&quot;队列为空，没有数据&quot;);
            return;
        }
        for (int i = 0; i &lt;arr.length ; i++) {
            System.out.println(&quot;arr[&quot;+i+&quot;]=&quot;+i+&quot;\n&quot;);
        }
    }
    public int headQueue(){
        //判断
        if (isEmpty()){
            throw  new RuntimeException((&quot;队列为空，没有数据&quot;));
        }
        return arr[front+1];
    }
}

</code></pre>

<h3 id="循环队列">循环队列</h3>

<p>上面的顺序队列，有一个很大的问题，就是这个队列只能用一次，我们可以将上面的顺序队列进行改造,</p>

<p>循环队列，可以这么理解，同样五个位置，0 1 2 3 4 ，先来五个人，队列满了，这时候我找了第一个人，出去一个人，0位置就空出来了，然后0位置又可以进来一个人，不过，我已经从0到1位置了，我只能先服务 1 2  3  4 位置的人，才能回到0 服务最后来的这个人</p>

<p>属性肯定不变、改构造方法,默认 front =rear =0</p>

<pre><code class="language-java">public CircleArray (int arrMaxSize){
    maxSize = arrMaxSize;
    arr=new int [maxSize];
}
</code></pre>

<p>判断为空的条件不用变，当rear == front依然为空</p>

<p>判断队列是否为满的时候我们需要改变一下条件为：</p>

<pre><code class="language-java">(rear+1)%maxSize ==front
</code></pre>

<p>为什么要加一取模呢？</p>

<p>因为我们在加数据到队列的时候，是这样的当rear+1<maxSize的时候，进队，则直接rear++,当rear>= maxSize的时候 则rear =(rear+1)%maxSize，这样rear就能一直保持小于maxSize，也就是为什么上面需要那样写，rear可能是＜front</p>

<p>进队、添加数据到队列</p>

<pre><code class="language-java">public void addQueue(int n){
    //判断队列是否满
    if (isFull()){
        System.out.println(&quot;队列满，不能加入数据了&quot;);
        return;
    }
    //直接将数据加入
    arr[rear] =n;
    //将rear后移，这里考虑取模，当rear&gt;=maxSize的时候，rear=rear-maxSize
    rear =(rear+1)%maxSize;
}
</code></pre>

<p>同理出队的时候也要考虑取模，令front永远小于maxSize</p>

<pre><code class="language-java">//获取队列数据，出队列
public  int getQueue(){
    //判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException(&quot;队列空，不能取得数据&quot;);
    }
    int value = arr[front];
    front=(front+1)%maxSize;
    return value;
}
</code></pre>

<p>其余代码：</p>

<pre><code class="language-java">public class CircleArray {
    private int maxSize;//表示数组最大的容量
    //front变量的含义做一个调整: front 指向队列的第一个元素，arr[front%maxSize] 就是队列的第一个元素
    //front的初始值=0
    private int front; //队列头
    //rear变量的含义做一个调整 :rear 指向队列的最后一个位置，因为希望空出一个空间作为约定
    //rear的初始值=0
    private int rear; //队列尾
    private int[] arr; //存放数据，模拟队列
    public CircleArray (int arrMaxSize){
        maxSize = arrMaxSize;
        arr=new int [maxSize];
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear ==front;
    }
    //判断队列是否为满
    public boolean isFull(){
        return (rear+1)%maxSize ==front;
    }
    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if (isFull()){
            System.out.println(&quot;队列满，不能加入数据了&quot;);
            return;
        }
        //直接将数据加入
        arr[rear] =n;
        //将rear后移，这里考虑取模，当rear&gt;=maxSize的时候，rear=rear-maxSize
        rear =(rear+1)%maxSize;
    }
    //获取队列数据，出队列
    public  int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException(&quot;队列空，不能取得数据&quot;);
        }
        int value = arr[front];
        front=(front+1)%maxSize;
        return value;
    }
    //显示队列所有的数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println(&quot;队列为空，没有数据&quot;);
            return;
        }
        for (int i = front; i &lt;front+size() ; i++) {
            System.out.println(&quot;arr[&quot;+i%maxSize+&quot;]=&quot;+arr[i%maxSize]+&quot;\n&quot;);
        }
    }
    public int size(){
        return (rear+maxSize -front)%maxSize;
    }
    public int headQueue(){
        //判断
        if (isEmpty()){
            throw  new RuntimeException((&quot;队列为空，没有数据&quot;));
        }
        return arr[front];
    }
}

</code></pre>

                        </div>
						 
                        
<div class="post-archive">
    <ul class="post-copyright">
        <li><strong>原文作者：</strong><a rel="author" href="http://linxianqin.gitee.io">林贤钦</a></li>
        <li style="word-break:break-all"><strong>原文链接：</strong><a href="http://linxianqin.gitee.io/post/%E9%98%9F%E5%88%97/">http://linxianqin.gitee.io/post/%E9%98%9F%E5%88%97/</a></li>
        <li><strong>版权声明：</strong>本作品采用<a rel="license" href="https://linxianqin.gitee.io">知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议</a>进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。</li>
    </ul>
</div>
<br/>



                        

<div class="post-archive">
    <h2>See Also</h2>
    <ul class="listing">
        
        <li><a href="/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/">稀疏数组</a></li>
        
        <li><a href="/post/%E9%98%BF%E9%87%8C%E4%BA%91EasyExcel%E5%AE%9E%E7%8E%B0%E5%90%8E%E7%AB%AF%E5%AF%B9Excel%E7%9A%84%E8%AF%BB%E5%86%99%E6%93%8D%E4%BD%9C/">使用阿里云EasyExcel实现后端对Excel的读写操作</a></li>
        
        <li><a href="/post/%E9%98%BF%E9%87%8C%E4%BA%91oss%E5%AF%B9%E8%B1%A1%E5%AD%98%E5%82%A8%E6%9C%8D%E5%8A%A1%E5%AE%9E%E7%8E%B0/">阿里云oss对象存储服务实现</a></li>
        
        <li><a href="/post/%E6%B5%85%E8%B0%88springboot-Security-Jwt-%E5%AE%9E%E7%8E%B0token/">springBoot&#43;Security&#43;JWT&#43;Jpa&#43;Vue实现登录权限控制</a></li>
        
        <li><a href="/post/springSecurity%E7%9A%84session%E7%AE%A1%E7%90%86%E5%8F%8A%E5%AE%89%E5%85%A8%E9%85%8D%E7%BD%AE/">SpringSecurity的session管理及安全配置</a></li>
        
    </ul>
</div>


                        <div class="post-meta meta-tags">
                            
                            <ul class="clearfix">
                                
                                <li><a href="http://linxianqin.gitee.io/tags/java">java</a></li>
                                
                                <li><a href="http://linxianqin.gitee.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</a></li>
                                
                            </ul>
                            
                        </div>
                    </article>
                    
    

    
    
    <div class="post bg-white">
      <script src="https://utteranc.es/client.js"
            repo= "757610938/hugo-blogs-utterances"
            issue-term="pathname"
            theme="github-light"
            crossorigin="anonymous"
            async>
      </script>
    </div>
    
                </div>
            </div>
            <div id="secondary">
    <section class="widget">
        <form id="search" action="//www.google.com/search" method="get" accept-charset="utf-8" target="_blank" _lpchecked="1">
      
      <input type="text" name="q" maxlength="20" placeholder="Search">
      <input type="hidden" name="sitesearch" value="http://linxianqin.gitee.io">
      <button type="submit" class="submit icon-search"></button>
</form>
    </section>
    
    <section class="widget">
        <h3 class="widget-title">最近文章</h3>
<ul class="widget-list">
    
    <li>
        <a href="http://linxianqin.gitee.io/post/java-%E5%8F%8D%E5%B0%84/" title="Java 反射">Java 反射</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/java-%E9%93%BE%E8%A1%A8/" title="Java 链表">Java 链表</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E7%9F%AD%E4%BF%A1%E6%B3%A8%E5%86%8C%E5%92%8C%E5%BE%AE%E4%BF%A1%E7%99%BB%E5%BD%95%E7%9A%84%E5%AE%9E%E7%8E%B0/" title="短信注册和微信登录的实现">短信注册和微信登录的实现</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/OAuth2.0%E8%AE%A4%E8%AF%81%E6%8E%88%E6%9D%83%E5%8D%95%E7%82%B9%E7%99%BB%E5%BD%95/" title="OAuth2.0认证授权单点登录">OAuth2.0认证授权单点登录</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/Nacos%E6%9C%8D%E5%8A%A1%E6%B3%A8%E5%86%8C%E4%B8%AD%E5%BF%83/" title="Nacos服务注册中心">Nacos服务注册中心</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/SpringCloud%E5%BE%AE%E6%9C%8D%E5%8A%A1/" title="SpringCloud微服务">SpringCloud微服务</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%BF%E9%87%8C%E4%BA%91%E8%A7%86%E9%A2%91%E7%82%B9%E6%92%AD%E6%9C%8D%E5%8A%A1/" title="阿里云视频点播服务前后端实现">阿里云视频点播服务前后端实现</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%9F%E5%88%97/" title="队列">队列</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/" title="稀疏数组">稀疏数组</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%BF%E9%87%8C%E4%BA%91EasyExcel%E5%AE%9E%E7%8E%B0%E5%90%8E%E7%AB%AF%E5%AF%B9Excel%E7%9A%84%E8%AF%BB%E5%86%99%E6%93%8D%E4%BD%9C/" title="使用阿里云EasyExcel实现后端对Excel的读写操作">使用阿里云EasyExcel实现后端对Excel的读写操作</a>
    </li>
    
</ul>
    </section>

    

    <section class="widget">
        <h3 class="widget-title">分类</h3>
<ul class="widget-list">
    
    <li><a href="http://linxianqin.gitee.io/categories/JWT/">JWT (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/hugo/">hugo (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/java/">java (18)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/java8/">java8 (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/springCloud/">springCloud (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/springSecurity/">springSecurity (4)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/vue/">vue (5)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/yml/">yml (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构 (3)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E8%BD%AF%E4%BB%B6%E6%B5%8B%E8%AF%95/">软件测试 (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E9%98%BF%E9%87%8C%E4%BA%91/">阿里云 (4)</a></li>
    
</ul>
    </section>

    <section class="widget">
        <h3 class="widget-title">标签</h3>
<div class="tagcloud">
    
    <a href="http://linxianqin.gitee.io/tags/JWT/">JWT</a>
    
    <a href="http://linxianqin.gitee.io/tags/hugo/">hugo</a>
    
    <a href="http://linxianqin.gitee.io/tags/java/">java</a>
    
    <a href="http://linxianqin.gitee.io/tags/java8/">java8</a>
    
    <a href="http://linxianqin.gitee.io/tags/spring/">spring</a>
    
    <a href="http://linxianqin.gitee.io/tags/springBoot/">springBoot</a>
    
    <a href="http://linxianqin.gitee.io/tags/springCloud/">springCloud</a>
    
    <a href="http://linxianqin.gitee.io/tags/ssm/">ssm</a>
    
    <a href="http://linxianqin.gitee.io/tags/vue/">vue</a>
    
    <a href="http://linxianqin.gitee.io/tags/yml/">yml</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E8%BD%AF%E4%BB%B6%E6%B5%8B%E8%AF%95/">软件测试</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E9%98%BF%E9%87%8C%E4%BA%91/">阿里云</a>
    
</div>
    </section>

    
<section class="widget">
    <h3 class="widget-title">友情链接</h3>
    <ul class="widget-list">
        
        <li>
            <a target="_blank" href="https://www.cnki.net" title="中国知网">中国知网</a>
        </li>
        
        <li>
            <a target="_blank" href="https://linxianqin.com" title="个人的另一个博客网站(国内加载慢)">个人的另一个博客网站(国内加载慢)</a>
        </li>
        
    </ul>
</section>


    <section class="widget">
        <h3 class="widget-title">其它</h3>
        <ul class="widget-list">
            <li><a href="http://linxianqin.gitee.io/index.xml">文章 RSS</a></li>
        </ul>
    </section>
</div>
        </div>
    </div>
</div>
<footer id="footer">
    <div class="container">
        &copy; 2020 <a href="http://linxianqin.gitee.io">林贤钦 By 林贤钦</a>.
        Powered by <a rel="nofollow noreferer noopener" href="https://gohugo.io" target="_blank">Hugo</a>.
        <a href="https://www.flysnow.org/" target="_blank">Theme</a> based on <a href="https://github.com/rujews/maupassant-hugo" target="_blank">maupassant</a>.
        
    </div>
</footer>


    
    <script type="text/javascript">
        
        (function () {
            $("pre code").parent().addClass("line-numbers")
        }());

        window.MathJax = {
            tex2jax: {
                inlineMath: [['$', '$']],
                processEscapes: true
                }
            };
    </script>
    <script type="text/javascript" src="/js/prism.js" async="true"></script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>


<a id="rocket" href="#top"></a>
<script type="text/javascript" src="/js/totop.js?v=0.0.0" async=""></script>

<script type="application/javascript">
var doNotTrack = false;
if (!doNotTrack) {
	window.ga=window.ga||function(){(ga.q=ga.q||[]).push(arguments)};ga.l=+new Date;
	ga('create', 'GA ID', 'auto');
	
	ga('send', 'pageview');
}
</script>
<script async src='https://www.google-analytics.com/analytics.js'></script>



    <script type="text/javascript" src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" async></script>




</body>
</html>
